1. Field of the Invention
The present invention relates to a transmission apparatus and method, reception apparatus and method, and program, and specifically, relates to a transmission apparatus and method, reception apparatus and method, and program whereby a more appropriate generating polynomial can be employed by being switched according to the data to be processed.
2. Description of the Related Art
With an information recording apparatus, communication apparatus, and so forth, when transmitting information (data) through a transmission line, the transmitted information sometimes includes an error.
There is a CRC (Cyclic Redundancy Check) as a technique widely employed serving as a method for detecting whether or not the information includes an error. In order to perform CRC, information to be transmitted has to be subjected to CRC encoding beforehand. CRC encoding will be described with reference to FIG. 1.
In FIG. 1, a transmission apparatus 1 and reception apparatus 3 are connected through a transmission line 2. CRC is employed for detection of error correction by error correction decoding by subjecting a CRC code obtained by adding a CRC parity to an information word (data) to error correction encoding such as the Reed-Solomon code or the like, with the transmission apparatus 1.
With the transmission apparatus 1, input information series wherein multiple information words (data) are continued, serving as a CRC encoding target to be transmitted, are input to a CRC encoder 11, and are subjected to CRC encoding. The details of the CRC encoder 11 will be described later with reference to FIG. 2. The information subjected to CRC encoding is input to an error correction encoder 12, and is subjected to error correction encoding such as Reed-Solomon Code or the like. The information subjected to error correction encoding is input to a transmission line encoder 13, subjected to transmission line encoding processing according to a transmission line 2, and transmitted to the transmission line 2.
The signal passed through the transmission line 2 is detected by a code detector 31 of the reception apparatus 3, and the detected information is input to a transmission line decoder 32. The detected information series subjected to transmission line decoding by the transmission line decoder 32 are subjected to error correction such as the Reed-Solomon code or the like, which corresponds to the processing of the error correction encoder 12, by the error correction decoder 33. The error-corrected information is next input to a CRC detector 34. The CRC detector 34 subjects the error-corrected detected series to CRC processing, determines whether or not error correction is correctly performed (whether or not the detected series include an error), and outputs the result thereof as a matching signal. The details of the CRC detector 34 will be described later with reference to FIG. 5.
The matching signal output from the CRC detector 34 is employed for improvement in reliability by performing a retransmission request with a controller of a drive of an information recording apparatus, for example.
As other applications of CRC codes, a CRC code is employed as part of a post processor with a code detector, or and is employed for header information, a transmission packet with packet communication. Also, a CRC code is employed as an elimination flag for error correction.
Error Detection Principle Employing CRC Code
Error detection principle employing a CRC code will be described. When an r-bit parity is added to an information word (data) made up of k bits to obtain a code word of a code length n (n=k+r) bits, a (k−1) order information polynomial M(x) wherein the information word is represented with a polynomial is multiplied by x′. For example, in a case wherein the information is “1010101” in binary, the information polynomial M(x) is represented with x6+x4+x2+1.
A result M(x)·x′ wherein the information polynomial M(x) is multiplied by x′ is obtained in accordance with the following Expression (1) by employing a remainder polynomial R(x) (order is (r−1) order) at the time of dividing by an r-order generating polynomial G(x), and a quotient polynomial Q(x), thereby making up an (n−1) order code polynomial W(x) such as the following Expression (2).M(x)·x′=Q(x)·G(x)+R(x)  (1)W(x)=M(x)·x′−R(x)  (2)
The code polynomial becomes W(x)=Q(x)·G(x) from a relation between Expressions (1) and (2). Accordingly, the code polynomial W(x) can be divided by the generating polynomial G(x) without a remainder.
According to the above-mentioned perspective, for example, when the reception apparatus 3 receives a polynomial (hereafter, referred to as “reception polynomial Y(x)”) which is the code polynomial W(x) which the transmission apparatus 1 in FIG. 1 transmitted to the reception apparatus 3 through the transmission line 2, the CRC detector 34 of the reception apparatus 3 determines whether or not the reception polynomial Y(x) can be divided by the generating polynomial G(x) without a remainder.
When the reception polynomial Y(x) can be divided by the generating polynomial G(x) without a remainder, the reception polynomial Y(x) is identical to the code polynomial W(x), so it can be estimated that no error has occurred in the information word at the transmission line 2, but in a case wherein the reception polynomial Y(x) can be divided by the generating polynomial G(x) with a remainder, the reception polynomial Y(x) is not the code polynomial W(x), so determination can be made (estimation can be made) that an error has occurred in the information word at the transmission line 2.
A CRC code is a cyclic code, so as long as the generating polynomial G(x) is determined, for example, the circuit configuration of the CRC encoder 11 within the transmission apparatus 1 in FIG. 1 can be relatively readily configured as an apparatus by employing a shift register and an exclusive OR.
Example of CRC Encoder
Examples of the generating polynomial G(x) widely employed with the CRC includes G(x)=x16+x12+x5+1 based on the CRC-CCITT standard which is the 16-bit CRC, and G(x)=x16+x15+x2+1 based on the CRC-ANSI standard.
Description will be made below regarding a configuration example of the CRC encoder (CRC encoding circuit) 11 with the transmission apparatus 1 in FIG. 1 in the case of employing a generating polynomial G(x)=x3+x+1 when the number of parity bits (order) is r=3, with reference to FIG. 2.
FIG. 2 is a diagram illustrating a configuration example of the CRC encoder 11 for generating the code polynomial W(x) from the information polynomial M(x).
The CRC encoder 11 includes a CRC parity generator 110, first selector 111, second selector 112, and number-of-bits counter 113.
The CRC parity generator 110 generates an r-bit CRC parity regarding k-bit information bit series to output this to the first selector 111. A parity generating method at the CRC parity generator 110 will be described with reference to FIGS. 3 and 4.
The second selector 112 outputs the input information bit series based on a status control signal S1 from the number-of-bits counter 113 during a period wherein the k-bit information bit series are input to a “0” input terminal. Also, when input of the information bit series to the “0” input terminal is ended, the second selector 112 outputs the r-bit parity generated at the CRC parity generator 110 which is input to a “1” input terminal through the first selector 111. Thus, “k-bit information bit series” and subsequent “r-bit parity bit generated at the CRC parity generator 110 based on the information bit series” are output from the second selector 112 of the CRC encoder 11. Thus, the code bit series output from the second selector 112 becomes code bit series of a code length n=k+r, which are made up of “k-bit information bit series” and “r-bit parity bit”.
The CRC parity generator 110 and first selector 111 will be described. FIG. 3 illustrates a circuit example of the CRC parity generator 110 in the case of employing G(x)=x3+x+1 as the generating polynomial G(x).
The CRC parity generator 110 in FIG. 3 is connected with a first shift register R00, first exclusive OR (EXOR) circuit EXOR1, second shift register R01, third shift register R02, and second exclusive OR circuit EXOR2 in a cyclic manner, and the output of the second exclusive OR circuit EXOR2 is input to the first exclusive OR circuit EXOR1.
Note that a circuit diagram example of the CRC parity generator 110 in the case of employing the generating polynomial G(x)=x4+x3+x2+x+1 will be shown in FIG. 4.
The CRC parity generator 110 in FIG. 4 is connected with a first shift register R00, first exclusive OR (EXOR) circuit EXOR1, second shift register R01, second exclusive OR circuit EXOR2 in a cyclic manner, third shift register RO2, third exclusive OR circuit EXOR3, fourth shift register R03, and fourth exclusive OR circuit EXOR4, and the output of the fourth exclusive OR circuit EXOR4 is input to the first, second, and third exclusive OR circuits EXOR1, EXOR2, and EXOR3.
As illustrated in FIGS. 3 and 4, the CRC parity generator 110 is configured based on the generating polynomial G(x). In other words, as can be understood from the illustrations in FIGS. 3 and 4, as long as the generating polynomial G(x) is determined, the CRC parity generator 110 can be configured as a circuit wherein shift registers and exclusive OR circuits are connected in a cyclic manner, and the output of the exclusive OR circuit on the final stage, e.g., the output of the second exclusive OR circuit EXOR2 in FIG. 3 or fourth exclusive OR circuit EXOR4 in FIG. 4 is applied to the exclusive OR circuit on the previous stage thereof.
Description will be made below regarding the operation of the CRC parity generator 110 illustrated in FIG. 3. The operation of the CRC parity generator 110 illustrated in FIG. 4 is basically the same as the operation of the CRC parity generator 110 illustrated in FIG. 3. In FIG. 3, the information bit series represented with the information polynomial M(x) are input to the second exclusive OR circuit EXOR2 which is upstream of the third shift register R02 for each point-in-time, e.g., for each clock wherein a shift register is operated, in order from high-order term of information bit series one at a bit, whereby the bit series M(x)·x′ wherein the information polynomial M(x) is multiplied by x′ is input to the CRC parity generator 110.
Here, the initial values of the first through third shift registers R00, R01, and R02 are zero.
The values held at the first through third shift registers R00, R01, and R02 at the time of input of the zero-order terms of the information bit series to the CRC parity generator 110 being completed provide the coefficient of each order of the remainder polynomial R(x). That is to say, the remainder polynomial R(x) becomes R(x)=(content held in the R02)×x2+(content held in the R01)×x+(content held in the R00).
Therefore, an enable signal E0 output from an unshown control circuit in FIG. 2 becomes disable (inactive state) at the time of input of the zero-order terms of the information bit series to the CRC parity generator 110 being completed, the values held in the first through third shift registers R00, R01, and R02 of the CRC parity generator 110 are held, and output to the first selector 111.
In FIG. 2, for example, the output from the CRC parity generator 110 of which the circuit configuration is illustrated in FIG. 3 to three input terminals 00, 01, and 10 of the first selector 111 are the outputs R00out, R01out, and R02out of the respective shift registers R00, R01, and R02 of the CRC parity generator 110, and the first selector 111 selects one of the outputs R00out, R01out, and R02out from the CRC parity generator 110 input to the three input terminals 00, 01, and 10 in order in accordance with a first selection signal S0 output from the unshown control circuit in FIG. 2, and outputs this to the “1” input terminal of the second selector 112.
The second selector 112 selects the information bit series input to the “0” input terminal during a period wherein the k-bit information bit series is input to the “0” input terminal of the second selector 112 in accordance with a second selection signal S1 output from the number-of-bits counter 113 controlled from the unshown control circuit in FIG. 2, in other words, in accordance with the bit count value of the number-of-bits counter 113, and outputs the information bit series as is. On the other hand, the second selector 112 selects and outputs the output of the first selector 111 input to the “1” input terminal of the second selector 112, i.e., the parity generated in the CRC parity generator 110 at timing wherein input of the information bit series to the CRC parity generator 110 has been completed, and all of the parities have been generated.
Thus, for example, code bit series output from the second selector 112 of the CRC encoder 11 in FIG. 2 are, as described above, made up of “k-bit information bit series” and “r-bit parity bit”. Accordingly, the code bit series becomes code bit series of a code length n=k+r.
For example, with the transmission apparatus 1 in FIG. 1, as described above, the code bit series subjected to the CRC encoding at the CRC encoder 11 are input to the error correction encoder 12, and are subjected to, for example, error correction encoding such as the Reed-Solomon code or the like. The information subjected to error correction encoding is input to the transmission line encoder 13, and is subjected to transmission line encoding processing according to the transmission line 2, and is transmitted to the transmission line 2.
The signal passed through the transmission line 2 is detected by the code detector 31 of the reception apparatus 3, and the detected information is input to the transmission line decoder 32. The detected information series subjected to transmission line decoding by the transmission line decoder 32 are subjected to error correction by the error correction decoder 33. The error-corrected information is determined at the CRC detector 34 regarding whether or not the detected series include an error.
FIG. 5 is a diagram illustrating a configuration example of the CRC detector 34 for inspecting whether or not the reception polynomial Y(x) includes an error. The CRC detector 34 includes a CRC parity checker 341, and comparator 342.
The CRC parity checker 341 examines, as described above, whether or not the reception polynomial Y(x) can be divided by the generating polynomial G(x) without a reminder, and in a case wherein the reception polynomial Y(x) can be divided by the generating polynomial G(x) without a reminder, the reception polynomial Y(x) is identical to the code polynomial W(x), and accordingly, determines that no error has occurred in the information word at the transmission line 2, but in a case wherein the reception polynomial Y(x) can be divided by the generating polynomial G(x) with a reminder, the reception polynomial Y(x) is not identical to the code polynomial W(x), so determines that an error has occurred in the information word at the transmission line 2.
The CRC parity checker 341 is a circuit for dividing the reception polynomial Y(x) by the generating polynomial G(x), and the comparator 342 is a circuit for determining whether or not the result divided by the CRC parity checker 341 includes a remainder.
FIG. 6 illustrates a configuration example of the CRC parity checker 341. The configuration of the CRC parity checker 341 illustrated in FIG. 6 corresponds to the CRC parity generator 110 illustrated in FIG. 3. In a case wherein the CRC parity generator 110 has the circuit configuration in FIG. 4, the CRC parity checker 341 also has a circuit configuration according thereto. Description will be made below regarding the CRC parity checker 341 corresponding to the CRC parity generator 110 illustrated in FIG. 3.
The CRC parity checker 341 illustrated in FIG. 6 is connected with a first exclusive OR circuit EXOR11, first shift register R10, second exclusive OR circuit EXOR12, second shift register R11, and third shift register R12 in a cyclic manner, and has a circuit configuration wherein the output of the third shift register R12 is input to the second exclusive OR circuit EXOR12.
With the CRC parity checker 341 in FIG. 6, the reception bit series represented with the reception polynomial Y(x) are input to the first exclusive OR circuit EXOR11 on the right edge of the first shift register R10 one bit at a time in order from a high order term for each point-in-time. The values held at the first through third shift registers R10, R11, and R12 at the time of input of the zero-order terms of the reception bit series to the CRC parity checker 341 being completed provide the coefficients of the remainder polynomial R(x). That is to say, R(x)=(value of the R12)×x2+(value of the R11)×x+(value of the R10). Here, the initial values of the first through third shift registers R10, R11, and R12 are zero.
In FIG. 5, the outputs R11 out, R11 out, and R12out to the comparator 342 from the CRC parity checker 341 are the outputs of the respective registers R10, R11, and R12 of the CRC parity checker 341 in FIG. 6.
The comparator 342 compares (determines) whether or not all of the values of the R10out, R11out, and R12out are zero, i.e., the remainder is zero, and outputs a one-bit matching signal representing whether or not all of the values of the R10out, R11out, and R12out are zero. That is to say, in a case wherein all of the values of the R10out, R11out, and R12out are zero, the reception polynomial Y(x) is identical to the code polynomial W(x), for example, a matching signal of logic “1” representing that determination is made that no error has occurred in the information word at the transmission line 2 is output from the comparator 342, or otherwise, for example, a matching signal of logic “0” is output.
The error detection capability of the CRC is generally evaluated with random error detection capability, burst error detection capability, and undetected error probability Pud for codes and is determined with the generating polynomial G(x) and code length n.
Now, the undetected error probability Pud for codes means probability wherein determination is made that there is no error in spite of the reception word changing to a code word different from the transmitted code word (a cord word wherein a CRC parity is calculated as to an information bit different from the provided information bit) due to an error occurred on the transmission line. The original code word is changed to a different code word, and accordingly, the remainder becomes zero even if the CRC is employed. That is to say, there is a case wherein while the reception word includes an error, determination is made that there is no error.
For example, as disclosed in J. K. Wolf, R. D. Blakeney, “An exact evaluation of the probability of undetected error for certain shortened binary CRC codes,” Military Communications Conference, 1988, MILCOM 88, Conference record, ‘21st Century Military Communications—What's Possible?’, 1988 IEEE, vol. 1, pp. 287-292, October 1988, the undetected error probability Pud for codes are represented with order (number of parities) r, code length n, a weight distribution A obtained by the generating polynomial G(x) and code length n being determined, or a dual code weight distribution B, and channel bit error probability (transition probability) ε at a binary symmetric channel, such as the following.
                              P          ud                =                              ∑                          i              =              1                        n                    ⁢                                    A              i                        ⁢                                                            ɛ                  i                                ⁡                                  (                                      1                    -                    ɛ                                    )                                                            n                -                i                                                                        (        3        )                                          P          ud                =                                            2                              -                r                                      ⁢                                          ∑                                  i                  =                  0                                n                            ⁢                                                                    B                    i                                    ⁡                                      (                                          1                      -                                              2                        ⁢                        ɛ                                                              )                                                  i                                              -                                    (                              1                -                ɛ                            )                        n                                              (        4        )            
With regard to the random error detection capability, all the (dmin−1) or less errors can be detected. However, a great number of errors other than those can be detected.
Also, with regard to the burst error detection capability, all the errors of which the length is the order of the generating polynomial G(x) or less can be detected. However, even with regard to burst errors of which the length is greater than the order of the generating polynomial, most of the errors can be detected.
With J. K. Wolf, R. D. Blakeney, “An exact evaluation of the probability of undetected error for certain shortened binary CRC codes,” Military Communications Conference, 1988, MILCOM 88, Conference record, ‘21st Century Military Communications—What's Possible?’, 1988 IEEE, vol. 1, pp. 287-292, October 1988, T. Baicheva, S. Dodunekov, “Undetected error probability performance of cyclic redundancy-check codes of 16-bit redundancy,” IEE Proc. Comm., vol. 147, no. 5, pp. 253-256, October 2000, P. Kazakov, “Fast Calculation of the Number of Minimum-Weight Words of CRC Codes,” IEEE Trans. Inform. Theory, vol. 47, no. 3, pp. 1190-1195, March 2001, P. Koopman, “Cyclic Redundancy Code (CRC) Polynomial Selection For Embedded Networks,” The International Conference on Dependable System and Networks, DSN-2004, G. Castagnoli, J. Ganz, P. Graber, “Optimum Cyclic Redundancy-Check Codes with 16-Bit Redundancy,” IEEE Trans. Comm., vol. 38, no. 1, pp. 111-114, January 1990, G. Funk, “Determination of Best Shortened Codes,” IEEE Trans. Comm., vol. 44, no. 1, pp. 1-6, January 1996, D. Chun, J. K. Wolf, “Special Hardware for Computing the Probability of Undetected Error for Certain CRC Codes and Test Results,” IEEE Trans. Comm., vol. 42, no. 10, pp. 2769-2772, October 1994, and G. Castagnoli, S. Brauer, M. Herrmann, “Optimum of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits,” IEEE Trans. Comm., vol. 41, no. 6, pp. 883-892, June 1993, various reports have been made regarding a generating polynomial for minimizing undetected error probability for codes, and various generating polynomials have been proposed according to the order (number of parities) of a generating polynomial and code length.
With T. Baicheva, S. Dodunekov, “Undetected error probability performance of cyclic redundancy-check codes of 16-bit redundancy,” IEE Proc. Comm., vol. 147, no. 5, pp. 253-256, October 2000, and P. Kazakov, “Fast Calculation of the Number of Minimum-Weight Words of CRC Codes,” IEEE Trans. Inform. Theory, vol. 47, no. 3, pp. 1190-1195, March 2001, a generating polynomial has been proposed wherein with the 16-bit CRC, undetected error probability for codes is suppressed to the minimum as to each code length.
Also, with G. Castagnoli, J. Ganz, P. Graber, “Optimum Cyclic Redundancy-Check Codes with 16-Bit Redundancy,” IEEE Trans. Comm., vol. 38, no. 1, pp. 111-114, Jan. 1990, and G. Castagnoli, S. Brauer, M. Herrmann, “Optimum of Cyclic Redundancy-Check Codes with 24 and 32 Parity Bits,” IEEE Trans. Comm., vol. 41, no. 6, pp. 883-892, June 1993, it has been confirmed that the undetected error probability Pud for codes exhibit properties wherein when the code length n changes, the undetected error probability Pud for codes enormously increases with a code length wherein the minimum hamming distance dmin for codes changes as a boundary.
FIG. 7 is a graph illustrating the minimum (limited) undetected error probability properties in the case of the 8-bit CRC as an example. In FIG. 7, the horizontal axis indicates the code length n (bits), and the vertical axis indicates the undetected error probability Pud for codes. This will be referred to as n-Pud properties.
With J. M. Stein, “METHOD FOR SELECTING CYCLIC REDUNDANCY CHECK POLYNOMIALS FOR LINEAR CODED SYSTEMS”, U.S. Pat. No. 6,085,349, Qaulcomm Incorporated, Filed Aug. 27, 1997, an invention relating to a selecting method of a CRC generating polynomial has been disclosed.
With J. M. Stein, “METHOD FOR SELECTING CYCLIC REDUNDANCY CHECK POLYNOMIALS FOR LINEAR CODED SYSTEMS”, U.S. Pat. No. 6,085,349, Qaulcomm Incorporated, Filed Aug. 27, 1997, when the order of a generating polynomial is given, a generating polynomial is selected based on a distance spectrum calculated for all of the generating polynomials of the order thereof. This distance spectrum is a table representing the number of code words at each of hamming distances. Thus, a generating polynomial having the maximum minimum hamming distance is selected, and a generating polynomial for minimizing the undetected error probability for codes is selected.